import java.util.ArrayList;
import java.util.List;

public class code5_5 {
    //每次可以爬 1阶 或 2阶，求 到第n阶的所有爬法路径
    public List<List<Integer>> climbStairsPaths(int n) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(n,0,new ArrayList<>(),res);
        return res;
    }

//    n 是 终点
//    current 是 当前位置
//    path 是 当前走法
//    res 是 所有结果

    private void dfs(int n, int current, ArrayList<Integer> path, List<List<Integer>> res) {
        if (current == n) {
            res.add(new ArrayList<>(path));
            return;
        }

        if (current > n ) return;

        for (int step = 1; step <= 2; step++) {
            path.add(step);
            dfs(n,current+step,path,res);
            path.remove(path.size()-1);//回溯
        }
    }
}
